const maxDistance = 3;

function editDistance(a, b) {
    // https://en.wikipedia.org/wiki/Damerau–Levenshtein_distance
    // Calculating optimal string alignment distance, no substring is edited more than once.
    // (Simple implementation.)

    // Quick early exit, return worst case.
    if (Math.abs(a.length - b.length) > maxDistance) return Math.max(a.length, b.length);

    // distance between prefix substrings of a and b
    const d = [];

    // pure deletions turn a into empty string
    for (let i = 0; i <= a.length; i++) {
        d[i] = [i];
    }
    // pure insertions turn empty string into b
    for (let j = 0; j <= b.length; j++) {
        d[0][j] = j;
    }

    // fill matrix
    for (let j = 1; j <= b.length; j++) {
        for (let i = 1; i <= a.length; i++) {
            let cost = 1;
            if (a[i - 1] === b[j - 1]) {
                cost = 0;
            } else {
                cost = 1;
            }
            d[i][j] = Math.min(
                d[i - 1][j] + 1, // deletion
                d[i][j - 1] + 1, // insertion
                d[i - 1][j - 1] + cost // substitution
            );
            // transposition
            if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
                d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + 1);
            }
        }
    }

    return d[a.length][b.length];
}

/**
 * Find close matches, restricted to same number of edits.
 *
 * @param {string} word
 * @param {string[]} candidates
 * @returns {string}
 */

function suggestSimilar(word, candidates) {
    if (!candidates || candidates.length === 0) return '';
    // remove possible duplicates
    candidates = Array.from(new Set(candidates));

    const searchingOptions = word.startsWith('--');
    if (searchingOptions) {
        word = word.slice(2);
        candidates = candidates.map((candidate) => candidate.slice(2));
    }

    let similar = [];
    let bestDistance = maxDistance;
    const minSimilarity = 0.4;
    candidates.forEach((candidate) => {
        if (candidate.length <= 1) return; // no one character guesses

        const distance = editDistance(word, candidate);
        const length = Math.max(word.length, candidate.length);
        const similarity = (length - distance) / length;
        if (similarity > minSimilarity) {
            if (distance < bestDistance) {
                // better edit distance, throw away previous worse matches
                bestDistance = distance;
                similar = [candidate];
            } else if (distance === bestDistance) {
                similar.push(candidate);
            }
        }
    });

    similar.sort((a, b) => a.localeCompare(b));
    if (searchingOptions) {
        similar = similar.map((candidate) => `--${candidate}`);
    }

    if (similar.length > 1) {
        return `\n(你需要的是 ${similar.join(', ')} 之一吗?)`;
    }
    if (similar.length === 1) {
        return `\n(你需要的是 ${similar[0]} 吗?)`;
    }
    return '';
}

exports.suggestSimilar = suggestSimilar;
